home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cocktail / docme.lha / doc.me / toolsupp.me < prev    next >
Text File  |  1992-09-25  |  45KB  |  1,544 lines
  1. .\" use: pic | tbl | eqn | ditroff -me
  2. .\"
  3. .\"    "@(#)bibmac.me    2.2    9/9/83";
  4. .de IP
  5. .ip \\$1 \\$2
  6. ..
  7. .de LP
  8. .lp
  9. ..
  10. .\"    @(#)bmac.std    2.2    9/9/83;
  11. .\" standard format troff commands
  12. .\" citation formatting strings
  13. .ds [[ [
  14. .ds ]] ]
  15. .ds ], ,\|
  16. .ds ]- -
  17. .ds [. " \&
  18. .ds .] .
  19. .ds [, " \&
  20. .ds ,] ,
  21. .ds [? " \&
  22. .ds ?] ?
  23. .ds [: " \&
  24. .ds :] :
  25. .ds [; " \&
  26. .ds ;] ;
  27. .ds [! " \&
  28. .ds !] !
  29. .ds [" " \&
  30. .ds "] \&"
  31. .ds [' " \&
  32. .ds '] '
  33. .ds [< " \&
  34. .ds >]
  35. .\" reference formmating strings
  36. .ds a] " \&
  37. .ds b] , \&
  38. .ds c] , \&
  39. .ds n] "\& and \&
  40. .ds m] "\& and \&
  41. .ds p] .
  42. .\" reference formmating macros
  43. .de s[   \" start reference
  44. .nh
  45. .IP [\\*([F] 5m
  46. ..
  47. .de e[   \" end reference
  48. .[-
  49. ..
  50. .de []   \" start to display collected references
  51. .LP
  52. ..
  53. .de ][   \" choose format
  54. .ie !"\\*([J"" \{\
  55. .    ie !"\\*([V"" .nr t[ 1    \" journal
  56. .    el            .nr t[ 5    \" conference paper
  57. .\}
  58. .el .ie !"\\*([B"" .nr t[ 3    \" article in book
  59. .el .ie !"\\*([R"" .nr t[ 4    \" technical report
  60. .el .ie !"\\*([I"" .nr t[ 2    \" book
  61. .el                .nr t[ 0    \" other
  62. .\\n(t[[
  63. ..
  64. .de 0[   \" other
  65. .s[
  66. .if !"\\*([A"" \\*([A\\c
  67. .if !"\\*([T"" , \\*([T\\c
  68. .if !"\\*([V"" , Vol. \\*([V\\c
  69. .if !"\\*([O"" , \\*([O\\c
  70. .if !"\\*([D"" , \\*([D\\c
  71. \&.
  72. .e[
  73. ..
  74. .de 1[ \" journal article
  75. .s[
  76. .if !"\\*([A"" \\*([A,
  77. .if !"\\*([T""  \\*([T,
  78. \\fI\\*([J \\*([V\\fP\c
  79. .if !"\\*([N"" ,\\*([N
  80. .if !"\\*([D"" (\\*([D)\c
  81. .if !"\\*([P"" , \\*([P\c
  82. .if !"\\*([I"" , \\*([I\c
  83. \\&.
  84. .if !"\\*([O"" \\*([O.
  85. .e[
  86. ..
  87. .de 2[ \" book
  88. .s[
  89. .ie !"\\*([A"" \\*([A,
  90. .el .if !"\\*([E"" \{\
  91. .       ie \\n([E-1 \\*([E, eds.,
  92. .       el \\*([E, ed.,\}
  93. .if !"\\*([T"" \\fI\\*([T\\fP,
  94. .rm a[
  95. .if !"\\*([I"" .ds a[ \\*([I
  96. .if !"\\*([C"" \{\
  97. .       if !"\\*(a["" .as a[ , \\&
  98. .       as a[ \\*([C\}
  99. .if !"\\*([D"" \{\
  100. .       if !"\\*(a["" .as a[ , \\&
  101. .       as a[ \\*([D\}
  102. \\*(a[.
  103. .if !"\\*([G"" Gov. ordering no. \\*([G.
  104. .if !"\\*([O"" \\*([O.
  105. .e[
  106. ..
  107. .de 3[ \" article in book
  108. .s[
  109. .if !"\\*([A"" \\*([A,
  110. .if !"\\*([T"" \\*([T,
  111. in \\fI\\*([B\\fP\c
  112. .if !"\\*([V"" , vol. \\*([V
  113. .if !~\\*([E~~ \{\
  114. .       ie , \\n([E-1  \\*([E (editors)\c
  115. .       el , \\*([E (editor)\c\}
  116. .if !"\\*([I"" , \\*([I\c
  117. .if !"\\*([C"" , \\*([C\c
  118. .if !"\\*([D"" , \\*([D\c
  119. .if !"\\*([P"" , \\*([P\c
  120. \\&.
  121. .if !"\\*([O"" \\*([O.
  122. .e[
  123. ..
  124. .de 4[ \" report
  125. .s[
  126. .if !"\\*([A"" \\*([A,
  127. .if !~\\*([E~~ \{\
  128. .       ie \\n([E-1 \\*([E, editors.
  129. .       el \\*([E, editor.\}
  130. \\*([T,
  131. \\*([R\c
  132. .if !"\\*([G"" \& (\\*([G)\c
  133. .if !"\\*([I"" , \\*([I\c
  134. .if !"\\*([C"" , \\*([C\c
  135. .if !"\\*([D"" , \\*([D\c
  136. \\&.
  137. .if !"\\*([O"" \\*([O.
  138. .e[
  139. ..
  140. .de 5[ \" conference paper
  141. .s[
  142. .if !"\\*([A"" \\*([A,
  143. .if !"\\*([T"" \\*([T,
  144. \\fI\\*([J\\fP,
  145. .if !"\\*([C"" \\*([C,
  146. .if !"\\*([D"" \\*([D\c
  147. .if !"\\*([P"" , \\*([P\c
  148. \\&.
  149. .if !"\\*([O"" \\*([O.
  150. .e[
  151. ..
  152. .de [-   \" clean up after yourself
  153. .rm [A [B [C [D
  154. .rm [E [F [G
  155. .rm [I [J [K
  156. .rm [N [O [P
  157. .rm [R [T
  158. .rm [V [W
  159. ..
  160. .\"    @(#)bmac.std    2.2    8/24/83;
  161. .\" standard format troff commands
  162. .\" citation formatting strings
  163. .ds [[ [
  164. .ds ]] ]
  165. .ds ], ,\|
  166. .ds ]- -
  167. .ds [. " \&
  168. .ds .] .
  169. .ds [, " \&
  170. .ds ,] ,
  171. .ds [< " \&
  172. .ds >]
  173. .\" reference formmating strings
  174. .ds c] , \&
  175. .ds n] "" and \&
  176. .ds m] "" and \&
  177. .ds a] " \&
  178. .\" reference formmating macros
  179. .de s[   \" start reference
  180. .nh
  181. .IP [\\*([F] 5m
  182. ..
  183. .de e[   \" end reference
  184. .[-
  185. ..
  186. .de []   \" start to display collected references
  187. .SH
  188. References
  189. .LP
  190. ..
  191. .de ][   \" choose format
  192. .ie !"\\*([J"" \{\
  193. .    ie !"\\*([V"" .nr t[ 1    \" journal
  194. .    el            .nr t[ 5    \" conference paper
  195. .\}
  196. .el .ie !"\\*([B"" .nr t[ 3    \" article in book
  197. .el .ie !"\\*([R"" .nr t[ 4    \" technical report
  198. .el .ie !"\\*([I"" .nr t[ 2    \" book
  199. .el                .nr t[ 0    \" other
  200. .\\n(t[[
  201. ..
  202. .de 0[   \" other
  203. .s[
  204. .if !"\\*([A"" \\*([A,
  205. .if !"\\*([T"" \\*([T,
  206. .if !"\\*([O"" \\*([O\c
  207. .if !"\\*([D"" , \\*([D\c
  208. \&.
  209. .e[
  210. ..
  211. .de 1[ \" journal article
  212. .s[
  213. .if !"\\*([A"" \\*([A,
  214. .if !"\\*([T"" \\*([T,
  215. \\fI\\*([J \\*([V\\fP,
  216. .if !"\\*([N"" \\*([N
  217. .if !"\\*([D"" (\\*([D),
  218. .if !"\\*([P"" \\*([P\c
  219. .if !"\\*([I"" , \\*([I\c
  220. \\&.
  221. .if !"\\*([O"" \\*([O.
  222. .e[
  223. ..
  224. .de 2[ \" book
  225. .s[
  226. .ie !"\\*([A"" \\*([A,
  227. .el .if !"\\*([E"" \{\
  228. .       ie \\n([E-1 \\*([E, eds.,
  229. .       el \\*([E, ed.,\}
  230. .if !"\\*([T"" \\fI\\*([T\\fP,
  231. .rm a[
  232. .if !"\\*([I"" .ds a[ \\*([I
  233. .if !"\\*([C"" \{\
  234. .       if !"\\*(a["" .as a[ , \\&
  235. .       as a[ \\*([C\}
  236. .if !"\\*([D"" \{\
  237. .       if !"\\*(a["" .as a[ , \\&
  238. .       as a[ \\*([D\}
  239. \\*(a[.
  240. .if !"\\*([G"" Gov. ordering no. \\*([G.
  241. .if !"\\*([O"" \\*([O.
  242. .e[
  243. ..
  244. .de 3[ \" article in book
  245. .s[
  246. .if !"\\*([A"" \\*([A,
  247. .if !"\\*([T"" \\*([T,
  248. in \\fI\\*([B\\fP,
  249. .if !"\\*([V"" vol. \\*([V,
  250. .if !"\\*([E"" \\*([E (ed.),
  251. .if !"\\*([I"" \\*([I,
  252. .if !"\\*([C"" \\*([C,
  253. .if !"\\*([D"" \\*([D\c
  254. .if !"\\*([P"" , \\*([P\c
  255. \\&.
  256. .if !"\\*([O"" \\*([O.
  257. .e[
  258. ..
  259. .de 4[ \" report
  260. .s[
  261. .if !"\\*([A"" \\*([A,
  262. \\*([T,
  263. \\*([R\c
  264. .if !"\\*([G"" \& (\\*([G)\c
  265. .if !"\\*([I"" , \\*([I\c
  266. .if !"\\*([C"" , \\*([C\c
  267. .if !"\\*([D"" , \\*([D\c
  268. \\&.
  269. .if !"\\*([O"" , \\*([O.
  270. .e[
  271. ..
  272. .de 5[ \" conference paper
  273. .s[
  274. .if !"\\*([A"" \\*([A,
  275. .if !"\\*([T"" \\*([T,
  276. \\fI\\*([J\\fP,
  277. .if !"\\*([C"" \\*([C\c
  278. .if !"\\*([D"" , \\*([D\c
  279. .if !"\\*([P"" , \\*([P\c
  280. \\&.
  281. .if !"\\*([O"" , \\*([O.
  282. .e[
  283. ..
  284. .de [-   \" clean up after yourself
  285. .rm [A [B [C [D
  286. .rm [E [F [G
  287. .rm [I [J [K
  288. .rm [N [O [P
  289. .rm [R [T
  290. .rm [V [W
  291. ..
  292. .if t \{ \
  293. .pl 29.7c    \" page length
  294. .po 2.5c    \" page offset (left margin)
  295. .ll 16.5c    \" line length
  296. .lt 16.5c    \" title length
  297. .nr LL 16.5c
  298. .nr )l 29.7c
  299. .nr hm 2c
  300. .nr $r 9    \" factor for vertical spacing
  301. .nr $R \n($r
  302. .sz 12        \" font size
  303. .nr pp 12
  304. .nr sp 12
  305. .nr tp 12
  306. .nr fp 10
  307. .hc ~        \" hyphenation character
  308. .        \" Umlauts and sharp s
  309. .ds A \(A:
  310. .ds O \(O:
  311. .ds U \(U:
  312. .ds a \(a:
  313. .ds o \(o:
  314. .ds u \(u:
  315. .ds s \(ss
  316. .        \"  UMLAUT  \*:u, etc.
  317. .ds : \v'-0.6m'\h'(1u-(\\n(.fu%2u))*0.13m+0.06m'\z.\h'0.2m'\z.\h'-((1u-(\\n(.fu%2u))*0.13m+0.26m)'\v'0.6m'
  318. .\}
  319. .if n \{ \
  320. .po 0        \" page offset (left margin)
  321. .ll 78        \" line length
  322. .lt 78        \" title length
  323. .nr $r 4    \" factor for vertical spacing
  324. .nr $R \n($r
  325. .hc ~        \" hyphenation character
  326. .        \" Umlaute und scharfes s
  327. .ds A Ae
  328. .ds O Oe
  329. .ds U Ue
  330. .ds a ae
  331. .ds o oe
  332. .ds u ue
  333. .ds s sz
  334. .\}
  335. .de _
  336. \&\\$1\l'|0\(ul'\\$2
  337. ..
  338. .de FT        \" font for programs
  339. .ft C
  340. .sz -2
  341. ..
  342. .de FR
  343. .ft R
  344. .sz +2
  345. ..
  346. .de []        \" start to display collected references
  347. .uh References
  348. .lp
  349. ..
  350. .de $0        \" collect table of contents
  351. .(x
  352. .ta 2c
  353. .ie '\\$2''    \\$1
  354. .el \\$2.    \\$1
  355. .)x
  356. ..
  357. .de np
  358. .nr $p +1
  359. .ip \\n($p.
  360. ..
  361. .de SH
  362. .sp 0.5
  363. .in -3
  364. .r \\$1
  365. .sp 0.5
  366. .in +3
  367. ..
  368. .de PP
  369. .sp 0.5
  370. ..
  371. .de IP
  372. .ip \\$1 \\$2
  373. ..
  374. .de I
  375. .i \\$1
  376. ..
  377. .de TH
  378. ..
  379. .hc ~
  380. .ds ], , 
  381. .EQ
  382. delim off
  383. .EN
  384. .b " "
  385. .sp 1c
  386. .ta 9c
  387. .ft R
  388. .sz 12
  389. \l'17.1c'
  390. .nf
  391.  
  392.  
  393.     Tool Support for
  394.     Data Structures
  395.  
  396.     J. Grosch
  397.  
  398.  
  399. \l'17.1c'
  400. .sp 12.5c
  401. \l'17.1c'
  402. .ft H
  403. .nf
  404.     GESELLSCHAFT F\*UR MATHEMATIK
  405.     UND DATENVERARBEITUNG MBH
  406.  
  407.     FORSCHUNGSSTELLE F\*UR
  408.     PROGRAMMSTRUKTUREN
  409.     AN DER UNIVERSIT\*AT KARLSRUHE
  410. .r
  411. \l'17.1c'
  412. .bp
  413. .\" .oh ''Tool Support'%'
  414. .\" .eh ''Tool Support'%'
  415. .oh '''%'
  416. .eh '''%'
  417. .ce 99
  418. .sz 20
  419. .b " "
  420. .sp 2
  421. Project
  422. .sp
  423. .b "Compiler Generation"
  424. .sp
  425. .sz 12
  426. \l'15c'
  427. .sp
  428. .sz 16
  429. .b "Tool Support for Data Structures"
  430. .sp 2
  431. Josef Grosch
  432. .sp 2
  433. .sz 14
  434. Nov. 8, 1989
  435. .sp
  436. .sz 12
  437. \l'15c'
  438. .sp 2
  439. Report No. 17
  440. .sp 2
  441. Copyright \(co 1989 GMD
  442. .sp 2
  443. Gesellschaft f\*ur Mathematik und Datenverarbeitung mbH
  444. Forschungsstelle an der Universit\*at Karlsruhe
  445. Vincenz-Prie\*snitz-Str. 1
  446. D-7500 Karlsruhe
  447. .ce 0
  448. .fi
  449. .bp 1
  450. .ce 99
  451. .b "Tool Support for Data Structures"
  452. .sp
  453. Josef Grosch
  454. GMD Forschungsstelle an der Universit\*at Karlsruhe
  455. Vincenz-Prie\*snitz-Str. 1, D-7500 Karlsruhe, Germany
  456. Tel: +721-6622-26
  457. E-Mail: grosch@karlsruhe.gmd.de
  458. .ce 0
  459. .sp
  460. .uh Abstract
  461. Linked records are a general mechanism to build data structures like lists,
  462. trees, and graphs. Most high-level programming languages only provide the
  463. definition of record types, an operator for component selection, and
  464. allocation of record storage. We propose to specify complete graph structures
  465. by context-free grammars. A tool can be used to transform such a specification
  466. into a set of record type declarations and program code for features like
  467. denotations for record values, input and output for record values and
  468. complete graphs, or interactive browsers for data structures. We describe
  469. such a tool called 
  470. .i ast
  471. (generator for abstract syntax trees), its specification language, the
  472. advantages of this approach, and our current experiences. Currently, the main
  473. application is the specification of attributed abstract syntax trees within
  474. compilers. We finally discuss the relationship to related work.
  475. .sh 1 Introduction
  476. .pp
  477. Linked records are a general mechanism to build data structures like lists,
  478. trees, and graphs. Most high-level programming languages only provide the
  479. definition of record types, an operator for component selection, and
  480. allocation of record storage. Therefore, the treatment of compound data types
  481. in most high-level languages can be considered to be quite "low-level".
  482. Exceptions are very-high-level languages like e.\ g. SETL
  483. \*([[SDD86\*(]] which provides denotations
  484. (aggregates) and input/output operations for values of all data types, even
  485. compound ones like tuples, arrays, or sets.
  486. .pp
  487. We propose to raise the level of conventional languages somewhat by
  488. improving the declarations of data structures and by extending the set of
  489. operations available for compound data types. Declarations should not merely
  490. describe single records but also the relationships among them. Additional
  491. operations include denotations for record values (aggregates) as well as input and
  492. output for record values or complete data structures like graphs.
  493. Moreover, it is desirable to have commonly used operations for general data structures.
  494. These could range from reversing the
  495. elements of lists to interactive browsers for graphs which allow the
  496. inspection of the values of all fields of the nodes in a user-driven dialogue.
  497. .pp
  498. The structure of graphs can be specified conveniently by context-free
  499. grammars. A grammar rule describes a node type and a nonterminal a set of
  500. node types.
  501. .pp
  502. The above features could be incorporated into existing or future languages.
  503. This would of course be the kind of realization to prefer.
  504. However, today we have to live with languages like Modula-2 or C without those
  505. features. Therefore, a tool could produce a program
  506. module written in the concrete target language which defines the specified
  507. data structure by a set of record declarations and which implements the
  508. additional operations by generated procedures. This has the advantage that
  509. no changes to existing languages are necessary.
  510. .pp
  511. This paper presents such a tool called
  512. .i ast :
  513. generator for \fIa\fPbstract \fIs\fPyntax \fIt\fPrees\*([<\*([[Gro91\*(]]\*(>].
  514. The tool's name is derived from its main application in compiler
  515. construction where it is used for attributed abstract syntax trees.
  516. .i ast
  517. is implemented in Modula-2 as well as in C under UNIX and generates Modula-2 or C source
  518. modules. We describe the specification language of the tool, its output, its
  519. advantages, and our experiences. We also discuss related approaches.
  520. In the following we talk only about the data structure directed graph
  521. because lists and trees are special cases thereof. The examples use
  522. Modula-2 as target language.
  523. .sh 1 "Specification Language"
  524. .pp
  525. The structure of directed graphs is specified by a
  526. formalism based on context-free grammars.
  527. However, we use the classical terminology for graphs in defining the
  528. specification language. Its relationship to context-free grammars is
  529. discussed later.
  530. .sh 2 "Node Types"
  531. .pp
  532. A directed graph consists of
  533. .i nodes .
  534. A node may be related to other nodes in a so-called
  535. .i parent-child
  536. relation. Then the first node is called a
  537. .i parent
  538. node and the latter nodes are called
  539. .i child
  540. nodes. Nodes without a parent node are usually called
  541. .i root
  542. nodes, nodes without children are called
  543. .i leaf
  544. nodes.
  545. .pp
  546. The structure and the properties of nodes are described by
  547. .i "node types" .
  548. Every node belongs to a node type.
  549. A specification of a graph describes a finite number of node types.
  550. A node type specifies the names of the child nodes and the associated node
  551. types as well as the names of the attributes and the associated attribute types.
  552. .sh 2 Children
  553. .pp
  554. Children are distinguished by
  555. .i selector
  556. names which have to be unambiguous within one node type.
  557. The children are of a certain node type.
  558. .(b
  559. Example:
  560. .sp 0.5
  561. .FT
  562.    If        = Expr: Expr Then: Stats Else: Stats .
  563.    While     = Expr: Expr Stats: Stats .
  564. .)b
  565. The example introduces two node types called
  566. .i If
  567. and
  568. .i While .
  569. A node of type If has three children which are selected by the names
  570. .i Expr ,
  571. .i Then ,
  572. and
  573. .i Else.
  574. The children have the node types
  575. .i Expr ,
  576. .i Stats ,
  577. and
  578. .i Stats .
  579. If a selector name is equal to the associated name of the node type it can
  580. be omitted. Therefore, the above example can be abbreviated as follows:
  581. .(b
  582. .FT
  583.    If        = Expr Then: Stats Else: Stats .
  584.    While     = Expr Stats .
  585. .)b
  586. .sh 2 Attributes
  587. .pp
  588. As well as children, every node type can specify an arbitrary number of
  589. .i attributes
  590. of arbitrary types. Like children, attributes are characterized by a selector
  591. name and a certain type.
  592. The descriptions of attributes are enclosed in brackets. The attribute types
  593. are given by names taken from the target language. Missing attribute types
  594. are assumed to be int or INTEGER depending on the target language (C or Modula-2).
  595. Children and attributes can be given in any order.
  596. The type of an attribute can be a pointer to a node type. In contrast to children,
  597. .i ast
  598. does not follow such an attribute during a graph traversal. All attributes
  599. are considered to be neither tree nor graph structured. Only the user knows
  600. about this fact and therefore he/she should take care.
  601. .(b
  602. Example:
  603. .sp 0.5
  604. .FT
  605.    Binary    = Lop: Expr Rop: Expr [Operator: INTEGER] .
  606.    Unary     = Expr [Operator] .
  607.    IntConst  = [Value] .
  608.    RealConst = [Value: REAL] .
  609. .)b
  610. .sh 2 Extensions
  611. .pp
  612. To allow several alternatives for the types of children an
  613. .i extension
  614. mechanism is used. A node type may be associated with several other node types enclosed
  615. in angle brackets. The first node type is called
  616. .i base
  617. or
  618. .i super
  619. type and the latter types are called
  620. .i derived
  621. types or
  622. .i subtypes .
  623. A derived type can in turn be extended with no limitation of the nesting depth.
  624. The extension mechanism induces a subtype relation between node types.
  625. This relation is transitive.
  626. Where a node of a certain node type is required, either a node of this node type or a node of
  627. a subtype thereof is possible.
  628. .(b
  629. Example:
  630. .sp 0.5
  631. .FT
  632. Stats        = <
  633.    If        = Expr Then: Stats Else: Stats .
  634.    While     = Expr Stats .
  635. > .
  636. .)b
  637. .pp
  638. In the above example
  639. .i Stats
  640. is a base type describing nodes with neither children nor attributes.
  641. It has two derived types called
  642. .i If
  643. and
  644. .i While .
  645. Where a node of type Stats is required, nodes of types Stats, If, and While are possible.
  646. Where a node of type If is required, nodes of type If are possible, only.
  647. .pp
  648. Besides extending the set of possible node types, the extension mechanism has
  649. the property of extending the children and attributes of the base type.
  650. The derived types possess the children and attributes of the base type.
  651. They may define additional children and attributes. In other words they
  652. .i inherit
  653. the structure of the base type.
  654. The selector names of all children and attributes in an extension hierarchy have to be distinct.
  655. The syntax has been designed this way in order to allow single inheritance, only.
  656. .(b
  657. Example:
  658. .sp 0.5
  659. .FT
  660. Stats        = Next: Stats [Position: tPosition] <
  661.    If        = Expr Then: Stats Else: Stats .
  662.    While     = Expr Stats .
  663. > .
  664. .)b
  665. .pp
  666. Nodes of type
  667. .i Stats
  668. have one child selected by the name
  669. .i Next
  670. and one attribute named
  671. .i Position .
  672. Nodes of type
  673. .i While
  674. have three children with the selector names
  675. .i Next ,
  676. .i Expr ,
  677. and
  678. .i Stats
  679. and one attribute named
  680. .i Position.
  681. .pp
  682. A node of a base type like
  683. .i Stats
  684. usually does not occur in an abstract syntax tree for a complete program.
  685. Still,
  686. .i ast
  687. defines this node type. It could be used as placeholder for unexpanded
  688. nonterminals in incomplete programs which occur in applications like
  689. syntax directed editors.
  690. .sh 2 Modules
  691. .pp
  692. The specification of node types can be grouped into modules. This feature
  693. can be used to structure a specification or to extend an existing one. If a
  694. node type has already been declared the given children, attributes, and
  695. extensions are added to the existing declaration.
  696. Otherwise a new node type is introduced.
  697. .(b
  698. Example:
  699. .sp 0.5
  700. .FT
  701. MODULE my_version
  702. .sp 0.5
  703. Stats        = [Env: tEnv] <                    /* add attribute */
  704.    While     = Init: Stats Terminate: Stats .   /* add children  */
  705.    Repeat    = Stats Expr .                     /* add node type */
  706. > .
  707. .sp 0.5
  708. END my_version
  709. .)b
  710. .sh 2 Properties
  711. .pp
  712. Children and attributes can be given several properties by attaching
  713. keywords like INPUT or REVERSE.
  714. .i Input
  715. attributes receive a value at node-creation time, whereas non-input
  716. attributes may receive their values at later times.
  717. Input attributes are included into the parameter list of the
  718. node constructor procedures (see section 3). As a shorthand,
  719. every list of children and attributes may contain the symbol '->' to separate
  720. input from non-input items.
  721. The property
  722. .i reverse
  723. specifies how lists should be reversed. It is discussed in the next section.
  724. .sh 2 "Reversal of Lists"
  725. .pp
  726. Recursive node types like
  727. .i Stats
  728. in the abstract grammar of the example below describe lists of subtrees.
  729. There are some cases where it is convenient to be able to easily
  730. reverse the order of the subtrees in a list. The facility provided by
  731. .i ast
  732. is a generalization of an idea presented in\*([<\*([[Par88\*(]]\*(>].
  733. .pp
  734. Using LR parsers, one might be forced to parse a list using a left-recursive
  735. concrete grammar rule because of the limited stack size.
  736. The concrete grammar rules of the following examples are written in the
  737. input language of the parser generator
  738. .i lalr
  739. \*([[Gro88\*(],GrV88\*(]] which is similar to the one of
  740. YACC\*([<\*([[Joh75\*(]]\*(>]. The node constructor
  741. procedures within the semantic actions are the ones provided by
  742. .i ast
  743. (see section 3).
  744. .(b
  745. Example:
  746. .sp 0.5
  747. concrete grammar (with tree building actions):
  748. .sp 0.5
  749. .FT
  750. Stats:                         {$$ := mStats0 ();      } .
  751. Stats: Stats Stat ';'          {$$ := mStats1 ($2, $1);} .
  752. Stat : WHILE Expr DO Stats END {$$ := mWhile  ($2, ReverseTREE ($4));} .
  753. .)b
  754. .(b
  755. abstract grammar:
  756. .sp 0.5
  757. .FT
  758. Stats        = <
  759.    Stats0    = .
  760.    Stats1    = Stat Stats REVERSE .
  761. > .
  762. .)b
  763. Without the call of the procedure ReverseTREE and the property REVERSE
  764. a parser using the above concrete grammar would construct statement lists
  765. where the list elements are in the wrong order, because the last statement
  766. in the source would be the first one in the list. The WHILE rule represents a
  767. location where statement lists are used.
  768. .pp
  769. To easily solve this problem,
  770. .i ast
  771. can generate a procedure to reverse lists.
  772. The specification has to describe how this should be done.
  773. At most one child of every node type may be given the property
  774. .i reverse .
  775. The generated list reversal procedure ReverseTREE then reverses a list with
  776. respect to this indicated child.
  777. The procedure ReverseTREE has to be called exactly once for a list to be
  778. reversed. This is the case at the location where a complete list is included
  779. as subtree (e.\ g. in a WHILE statement).
  780. .sh 2 "Target Code"
  781. .pp
  782. An
  783. .i ast
  784. specification may include sections containing
  785. .i "target code" .
  786. Target code is code written in the target language which is copied unchecked
  787. and unchanged to certain places in the generated module.
  788. Target code can be used for import or export statements, for the declaration
  789. of global variables or procedures, and for statements to
  790. initialize or finalize the declared data structures.
  791. .sh 2 "Type Specific Operations"
  792. .pp
  793. Procedures generated by
  794. .i ast
  795. apply seven operations to attributes: initialization, finalization, ascii read
  796. and write, binary read and write, and copy (see Table 1).
  797. .i Initialization
  798. is performed whenever a node is created. It can range from
  799. assigning an initial value to the allocation of dynamic storage or the
  800. construction of complex data structures.
  801. .i Finalization
  802. is performed immediately before a node is deleted and may e. g. release
  803. dynamically allocated space. The
  804. .i read
  805. and
  806. .i write
  807. operations enable the readers and writers to handle the
  808. complete nodes including all attributes, even those of user-defined types.
  809. The operation
  810. .i copy
  811. is needed to duplicate values of attributes of user-defined types. By default,
  812. .i ast
  813. just copies the bytes of an attribute to duplicate it.
  814. Therefore, pointer semantics is assumed for attributes of a pointer type.
  815. If value semantics is needed, the user has to take care about this operation.
  816. .pp
  817. The operations are type specific in the sense that every type has its own
  818. set of operations. All attributes having the same type (target type name)
  819. are treated in the same way. Chosing different type names for one type
  820. introduces subtypes and allows to treat attributes of different subtypes
  821. differently. Type operations for the predefined types of a target language
  822. are predefined within
  823. .i ast .
  824. For user-defined types,
  825. .i ast
  826. assumes default operations (see Table 1).
  827. The procedures yyReadHex and
  828. yyWriteHex read and write the bytes of an attribute as hexadecimal values.
  829. The procedures yyGet and
  830. yyPut read and write the bytes of an attribute unchanged (without conversion).
  831. The operations are defined by a macro mechanism.
  832. TYPE is replaced by the concrete type name.
  833. .i a
  834. is a formal macro parameter referring to the attribute.
  835. It is possible to redefine the operations by including new macro definitions
  836. written in
  837. .i cpp
  838. syntax.
  839. .(b L
  840. .sp 0.5
  841. .ce
  842. Table 1: Type specific operations
  843. .sp 0.5
  844. .TS
  845. center;
  846. c | c | c s
  847. c | c | c | c
  848. l | l | l | l.
  849.         \h'2c'default macro
  850. operation    macro name    C    Modula-2
  851. _
  852. initialization    beginTYPE(a)
  853. finalization    closeTYPE(a)
  854. ascii read    readTYPE(a)    yyReadHex (& a, sizeof (a));    yyReadHex (a);
  855. ascii write    writeTYPE(a)    yyWriteHex (& a, sizeof (a));    yyWriteHex (a);
  856. binary read    getTYPE(a)    yyGet (& a, sizeof (a));    yyGet (a);
  857. binary write    putTYPE(a)    yyPut (& a, sizeof (a));    yyPut (a);
  858. copy    copyTYPE(a)
  859. .TE
  860. .)b
  861. .sh 1 "Generated Program Module and its Use"
  862. .pp
  863. A specification as described in the previous section is translated by
  864. .i ast
  865. into a program module consisting of a definition and an implementation part.
  866. Only the definition part is sketched here.
  867. The definition part contains primarily type declarations to
  868. describe the structure of the graphs and the headings of the generated
  869. procedures.
  870. .(z L
  871. .ce
  872. Table 2: Generated objects and procedures
  873. .sp 0.5
  874. .TS
  875. center;
  876. l | l.
  877. object/procedure    description
  878. _
  879. <node type>    named constant to encode a node type
  880. tTREE    pointer type, refers to variant record type describing all node types
  881. TREERoot    variable of type tTREE, can serve as root
  882.      (additional variables can be declared)
  883. _
  884. MakeTREE    node constructor procedure without attribute initialization
  885. n<node type>    node constructor procedures with attribute initialization
  886.      according to the type specific operations
  887. m<node type>    node constructor procedures with attribute initialization
  888.     from a parameter list for \fIinput\fP attributes
  889. ReleaseTREE    node or graph finalization procedure,
  890.     all attributes are finalized, all node space is deallocated
  891. ReleaseTREEModule    deallocation of all graphs managed by a module
  892. WriteTREENode    ASCII node writer procedure
  893. ReadTREE    ASCII graph reader procedure
  894. WriteTREE    ASCII graph writer procedure
  895. GetTREE    binary graph reader procedure
  896. PutTREE    binary graph writer procedure
  897. ReverseTREE    procedure to reverse lists
  898. TraverseTREETD    top down graph traversal procedure (reverse depth first)
  899. TraverseTREEBU    bottom up graph traversal procedure (depth first search)
  900. CopyTREE    graph copy procedure 
  901. CheckTREE    graph syntax checker procedure 
  902. QueryTREE    graph browser procedure 
  903. BeginTREE    procedure to initialize user-defined data structures
  904. CloseTREE    procedure to finalize user-defined data structures
  905. .TE
  906. .)z
  907. .pp
  908. Every node type is turned into a constant declaration and a record
  909. (struct) declaration. 
  910. That is quite simple, because node types and record declarations
  911. are almost the same concepts
  912. except for the extension mechanism and some shorthand notations.
  913. All these records become members of a variant record (union) used to describe
  914. graph nodes in general. This variant record has a tag field called
  915. .i Kind
  916. which stores the code of the node type.
  917. A pointer to the variant record is a type representing graphs.
  918. Like all generated names, this pointer type is derived from the name of the
  919. specification. Table 2 briefly explains the exported objects.
  920. Their generation is requested by simple command line options.
  921. .pp
  922. The parameters of the procedures
  923. .i "m<node type>"
  924. have to be given in the order of the
  925. .i input
  926. attributes in the specification. Attributes of the base type (recursively)
  927. precede the ones of the derived type.
  928. The procedures
  929. .i TraverseTREETD
  930. and
  931. .i TraverseTREEBU
  932. visit all nodes of a graph. At every node a procedure given as
  933. parameter is executed. An assignment of a graph to a variable of
  934. type
  935. .i tTREE
  936. can be done in two ways: The usual assignment operators '=' or ':=' yield pointer
  937. semantics. The procedure
  938. .i CopyTREE
  939. yields value semantics by duplicating a given graph.
  940. .pp
  941. The procedure
  942. .i QueryTREE
  943. allows to browse a graph and to inspect one node at a time. A node including
  944. the values of its attributes is printed on
  945. .i "standard output" .
  946. Then the user is prompted to provide one of the following commands from
  947. .i "standard input" :
  948. .(b
  949. .ta 3c
  950. parent    display parent node
  951. quit    quit procedure QueryTREE
  952. <selector>    display specified child
  953. .)b
  954. .pp
  955. Unfortunately, the typing rules of
  956. .i ast
  957. (see section 2.4.) can not be mapped to every target language. For example the subtype
  958. relation can not be expressed in Modula-2. A subtype has to be compatible with its base type.
  959. Two subtypes of one base type have to be incompatible.
  960. As a compromise, all node types without base
  961. types could be implemented by different pointer types. Extensions of a base type would be
  962. mapped to the same pointer type as the base type. This solution would implement half of
  963. .i ast's
  964. typing rules through static typing of the target language. For a full implementation, target
  965. languages with subtypes such as Oberon or C++ are necessary.
  966. .pp
  967. The current implementation of
  968. .i ast
  969. omits static type checking. It offers dynamic type checking through the procedure
  970. .i CheckTREE .
  971. This procedure has to be called explicitly
  972. to check if a graph is properly typed. In case of typing errors
  973. the involved parent and child nodes are printed on
  974. .i "standard error" .
  975. .pp
  976. The remainder of this section explains how to use the generated objects,
  977. presents the advantages of this approach, and reports early experience with
  978. the method.
  979. .pp
  980. Trees or graphs are created by successively creating their nodes. The easiest
  981. way is to call the constructor procedures m<node type>. These combine node
  982. creation, storage allocation, and attribute assignment.
  983. They provide a mechanism similar to record aggregates. Nested calls of
  984. constructor procedures allow programming with (ground) terms as in Prolog
  985. or LISP. The type of a node can be retrieved by
  986. examination of the predefined tag field called
  987. .i Kind .
  988. Children and attributes can be accessed using two record selections.
  989. The first one states the node type and the
  990. second one gives the selector name of the desired item.
  991. .(b
  992. Example:
  993. .sp 0.5
  994. abstract syntax:
  995. .sp 0.5
  996. .FT
  997. Expr         = [Position: tPosition] <
  998.    Binary    = Lop: Expr Rop: Expr [Operator: INTEGER] .
  999.    Unary     = Expr [Operator] .
  1000.    IntConst  = [Value] .
  1001.    RealConst = [Value: REAL] .
  1002. > .
  1003. .)b
  1004. .(b
  1005. tree construction by a term:
  1006. .sp 0.5
  1007. .FT
  1008. CONST Plus = 1;
  1009. VAR t: tTREE; Pos: tPosition;
  1010. .sp 0.5
  1011. t := mBinary (Pos, mIntConst (Pos, 2), mIntConst (Pos, 3), Plus);
  1012. .)b
  1013. .(b
  1014. tree construction during parsing:
  1015. .sp 0.5
  1016. .FT
  1017. Expr: Expr '+' Expr {$$.Tree := mBinary ($2.Pos, $1.Tree, $3.Tree, Plus);} .
  1018. Expr:      '-' Expr {$$.Tree := mUnary  ($1.Pos, $2.Tree, Minus);        } .
  1019. Expr: IntConst      {$$.Tree := mIntConst ($1.Pos, $1.IntValue);         } .
  1020. Expr: RealConst     {$$.Tree := mRealConst ($1.Pos, $1.RealValue);       } .
  1021. .)b
  1022. .(b
  1023. access of tag field, children, and attributes:
  1024. .sp 0.5
  1025. .FT
  1026. CASE t^.Kind OF
  1027. | Expr  : ... t^.Expr.Position             ...
  1028. | Binary: ... t^.Binary.Operator           ...
  1029.           ... t^.Binary.Lop                ...
  1030. | Unary : ... t^.Unary.Expr^.Expr.Position ...
  1031. END;
  1032. .)b
  1033. .pp
  1034. .i ast
  1035. can be used not only for abstract syntax trees in compilers but for every
  1036. tree or graph like data structure. In general the data structure can serve
  1037. as interface between phases within a program or between separate programs.
  1038. In the latter case it would be communicated via a file using the generated
  1039. reader and writer procedures.
  1040. .pp
  1041. Generated tree respectively graph modules have successfully been used in
  1042. compilers e.\ g. for MiniLAX\*([<\*([[WGS89\*(]]\*(>] and UNITY
  1043. \*([[Bie89\*(]] as well as for a Modula -> C translator\*([<\*([[Mar90\*(]]\*(>].
  1044. The modules for the internal data structure of
  1045. .i ast
  1046. itself and the attribute evaluator generator
  1047. .i ag
  1048. \*([[Gro89\*(]] have also been generated by
  1049. .i ast .
  1050. Moreover, the symbol table module of the Modula -> C translator has been
  1051. generated.
  1052. .pp
  1053. The advantage of this approach is that it saves considerably hand-coding of
  1054. trivial declarations and operations. Table 3 lists the sizes (numbers of
  1055. lines) of some specifications and the generated modules.
  1056. Sums in the specification column are composed of the sizes for
  1057. the definition of node types and for user-supplied target code.
  1058. Sums in the tree module column are composed of the sizes for the
  1059. definition part and for the implementation part.
  1060. The large sizes of the tree modules are due to the numerous
  1061. node constructor procedures and from the graph browser in the case of
  1062. .i ag .
  1063. These procedures proved to be very helpful for debugging purposes
  1064. as they provide readable output of complex data structures.
  1065. .(b L
  1066. .sp 0.5
  1067. .ce
  1068. Table 3: Examples of \fIast\fP applications
  1069. .sp 0.5
  1070. .TS
  1071. center;
  1072. l | r | r.
  1073. application    specification    tree module
  1074. _
  1075. MiniLAX             56    202 + \0835 = 1037
  1076. UNITY               210    207 + \0962 = 1169
  1077. Modula -> C            240    583 + 3083 = 3666
  1078. ag                 78 + 347 = 425    317 + 1317 = 1634
  1079. Symbol table    82 + 900 = 982    399 + 1431 = 1830
  1080. .TE
  1081. .)b
  1082. .pp
  1083. The realization of the presented concepts by a preprocessor leads to the mixture of generated
  1084. and hand-written program code. The debugging of such a program may be problematic. Of course,
  1085. the pure generated parts are correct. With the possibility to insert target code and type
  1086. specific operations errors might be introduced. These are detected by the compiler or during
  1087. run time and reported with respect to the generated program code instead of the
  1088. specification. Therefore, errors in this situation are hard to debug. This
  1089. problem could be solved by incorporating the concepts into a language instead of implementing
  1090. them by a preprocessor.
  1091. .sh 1 "Related Research"
  1092. .sh 2 "Variant Records"
  1093. .pp
  1094. .i ast
  1095. specifications and variant record types like in Pascal\*([<\*([[JWM85\*(]]\*(>]
  1096. or Modula-2\*([<\*([[Wir85\*(]]\*(>] are very similar. Every node type in an
  1097. .i ast
  1098. specification corresponds to a single variant. In the generated code, every
  1099. node type is translated into a record type. All record types become members
  1100. of a variant record type representing the type for the graph nodes.
  1101. .pp
  1102. The differences are the following:
  1103. .i ast
  1104. specifications are shorter than directly hand-written variant record types.
  1105. They are based on the formalism of context-free grammars (see section below).
  1106. The generator
  1107. .i ast
  1108. automatically provides operations on record types which would be simple but
  1109. voluminous to program by hand. The node constructor procedures allow
  1110. programming with record aggregates and provide dynamic storage management.
  1111. The reader and writer procedures supply input and output for record types
  1112. and even for complete linked data structures such as trees and graphs.
  1113. .sh 2 "Type Extensions"
  1114. .pp
  1115. Type extensions have been introduced with the language Oberon
  1116. \*([[Wir88a\*(],Wir88b\*(],Wir88c\*(]].
  1117. The extension mechanism of
  1118. .i ast
  1119. is basically the same as in Oberon.
  1120. The notions extension, base type, and derived type are equivalent (see Table 4).
  1121. .i "Type tests"
  1122. and
  1123. .i "type guards"
  1124. are not supported by
  1125. .i ast .
  1126. They can be programmed by inspecting the tag field of a node.
  1127. .i ast
  1128. does not provide assignment of subtypes to base types in the sense of value semantics or a
  1129. projection, respectively.
  1130. The tool can be seen as a preprocessor providing type extensions for Modula-2 and C.
  1131. .pp
  1132. The second example in section 2.4. illuminates the relationship between
  1133. .i ast
  1134. and Oberon. The node type
  1135. .i Stats
  1136. is a base type with two fields, a child and an attribute.
  1137. It is extended e. g. by the node type
  1138. .i While
  1139. with two more fields representing children.
  1140. .sh 2 "Context-Free Grammars"
  1141. .pp
  1142. As already mentioned,
  1143. .i ast
  1144. specifications are based on context-free grammars.
  1145. .i ast
  1146. specifications extend context-free grammars by selector names for right-hand
  1147. side symbols, attributes, the extension mechanism, and modules. If the
  1148. features are
  1149. omitted we basically arrive at context-free grammars. This holds from the
  1150. syntactic as well as from the semantic point of view. The names of the node
  1151. types represent both terminal or nonterminal symbols and rule names.
  1152. Node types correspond to grammar rules. The notions of derivation and
  1153. derivation tree can be used similarly in both cases. The selector names can
  1154. be seen as syntactic sugar and the attributes as some kind of terminal
  1155. symbols. The extension mechanism is equivalent to a shorthand notation for
  1156. factoring out common rule parts in combination with implicit chain rules.
  1157. .pp
  1158. Again referring to the second example in section 2.4.,
  1159. .i Stats
  1160. corresponds to a nonterminal. There are two rules or right-hand sides for
  1161. .i Stats
  1162. which are named
  1163. .i If
  1164. and
  1165. .i While .
  1166. The latter would be regarded as nonterminals, too, if a child of type
  1167. .i If
  1168. or
  1169. .i While
  1170. would be specified.
  1171. .sh 2 "Attribute Grammars"
  1172. .pp
  1173. Attribute grammars
  1174. \*([[Knu68\*(],Knu71\*(]] and
  1175. .i ast
  1176. specifications are based on context-free grammars and associate attributes with terminal
  1177. and nonterminals symbols. Additionally,
  1178. .i ast
  1179. allows attributes which are local to rules.
  1180. As the structure of the tree itself is known and transparent, subtrees can be
  1181. accessed or created dynamically and used as attribute values. The access of
  1182. the right-hand side symbols uses the selector names for symbolic access
  1183. instead of the grammar symbols with an additional subscript if needed.
  1184. There is no need to map chain rules
  1185. to tree nodes because of the extension mechanism offered by
  1186. .i ast.
  1187. Attribute evaluation is outside the scope of
  1188. .i ast .
  1189. This can be done either with the attribute evaluator generator
  1190. .i ag
  1191. \*([[Gro89\*(]] which understands
  1192. .i ast
  1193. specifications extended by attribute computation rules and processes the
  1194. trees generated by
  1195. .i ast
  1196. or by hand-written programs that use an
  1197. .i ast
  1198. generated module. In the latter case attribute computations do not have to
  1199. obey the single assignment restriction for attributes. They can assign a
  1200. value to an attribute zero, once, or several times.
  1201. .sh 2 "Interface Description Language (IDL)"
  1202. .pp
  1203. The approach of
  1204. .i ast
  1205. is similar to the one of IDL\*([<\*([[Lam87\*(],NNG89\*(]]\*(>].
  1206. Both specify attributed trees as well as graphs.
  1207. Node types without extensions are called nodes in IDL and node types with
  1208. extensions (base types) are called classes.
  1209. .i ast
  1210. has simplified this to the single notion of a node type.
  1211. Attributes are treated similarly in both systems.
  1212. Children and attributes are both regarded as attributes, as
  1213. structural and non-structural ones, with only little difference in between.
  1214. Whereas IDL in general allows multiple inheritance of attributes,
  1215. .i ast
  1216. is restricted to single inheritance and uses the notion extension instead
  1217. \*([[Wir88a\*(]].
  1218. IDL knows the predefined types INTEGER, RATIONAL, BOOLEAN, STRING, SEQ OF,
  1219. and SET OF. It offers special operations for the types SEQ OF and SET OF.
  1220. .i ast
  1221. really has no built in types at all, it uses the ones of the target language
  1222. and has a table containing the type specific operations e.\ g. for reading
  1223. and writing. Both
  1224. .i ast
  1225. and IDL allow attributes of user-defined types. In
  1226. .i ast
  1227. the type specific operations for predefined or user-defined
  1228. types are easily expressed by macros using the target language directly.
  1229. IDL offers an assertion language whereas
  1230. .i ast
  1231. does not. IDL provides a mechanism to modify existing specifications.
  1232. The module feature of
  1233. .i ast
  1234. can be used to extend existing specifications.
  1235. From
  1236. .i ast ,
  1237. readers and writers are requested with simple command line options instead of
  1238. complicated syntactic constructs.
  1239. .i ast
  1240. does not support representation specifications, because representations are
  1241. much more easily expressed using the types of the target language directly.
  1242. Summarizing, we consider
  1243. .i ast
  1244. to have a simpler specification method and to generate more powerful
  1245. features like aggregates, reversal of lists, and graph browsers.
  1246. .sh 2 "Object-Oriented Languages"
  1247. .pp
  1248. The extension mechanism of 
  1249. .i ast
  1250. is exactly the same as single inheritance in object-oriented languages like
  1251. e. g. Simula\*([<\*([[DMN70\*(]]\*(>] or Smalltalk\*([<\*([[Gol84\*(]]\*(>].
  1252. The hierarchy introduced by the extension mechanism corresponds
  1253. directly to the class hierarchy of object-oriented languages.
  1254. The notions
  1255. .i "base type"
  1256. and
  1257. .i superclass
  1258. both represent the same concept. Messages and virtual procedures are out of the scope of
  1259. .i ast.
  1260. Virtual procedures or object specific procedures might be simulated with
  1261. procedure-valued attributes.
  1262. Table 4 summarizes the corresponding notions of trees
  1263. (\fIast\fP), type extensions, and object-oriented programming.
  1264. .(b L
  1265. .sp 0.5
  1266. .ce
  1267. Table 4: Comparison of notions from the areas of trees, types, and object-oriented programming
  1268. .sp 0.5
  1269. .TS
  1270. center;
  1271. l | l | l.
  1272. trees    types    object-oriented programming
  1273. _
  1274. node type    record type    class
  1275. -    base type    superclass
  1276. -    derived type    subclass
  1277. attribute, child    record field    instance variable
  1278. tree node    record variable    object, instance
  1279. -    extension    inheritance
  1280. .TE
  1281. .)b
  1282. .sh 2 "Tree Grammars"
  1283. .pp
  1284. Conventional tree grammars are characterized by the fact that all
  1285. right-hand sides start with a terminal symbol. They are used for the
  1286. description of string languages that represent trees in prefix form.
  1287. .i ast
  1288. specifications describe trees which are represented by (absolute) pointers
  1289. from parent to child nodes. If we shift the names of node types of
  1290. .i ast
  1291. specifications to the beginning of the right-hand side and interpret them as
  1292. terminals we arrive at conventional tree grammars. That is exactly what is
  1293. done by the tree/graph writer procedures. They write a tree/graph in prefix
  1294. form and prepend every node with the name of its node type.
  1295. That is necessary to be able to perform the read operation.
  1296. .sh 1 Summary
  1297. .pp
  1298. We presented the tool
  1299. .i ast ,
  1300. a generator for abstract syntax trees, which supports the definition and
  1301. manipulation of graph-like data structures. The records which define a graph
  1302. and their relationships are specified by a formalism based on context-free
  1303. grammars. The data structures may be decorated with attributes of arbitrary
  1304. types. The tool generates a program module containing a set of
  1305. declarations to define the data structure and various procedures to
  1306. manipulate it. There are procedures to construct and destroy
  1307. nodes or graphs, to read and write graphs from (to) files, and to traverse
  1308. graphs in some commonly used manners. The mentioned readers and writers
  1309. process ascii as well as binary graph representations.
  1310. .pp
  1311. The advantages of this approach are: record aggregates are provided which
  1312. allow a concise notation for node creation. It is possible to build trees
  1313. by writing terms. The extension mechanism avoids chain rules and allows, for
  1314. example lists with elements of different types. Input/output procedures
  1315. for records and complete graphs are provided. The output procedures and the
  1316. interactive graph browser facilitate the debugging phase as they operate on
  1317. a readable level and know the data structure.
  1318. The user does not have to attend to algorithms for traversing graphs. He/she
  1319. is freed from the task of writing large amounts of relatively simple code.
  1320. All of these features significantly increase programmer productivity.
  1321. .fi
  1322. .[]
  1323. .[-
  1324. .ds [F Bie89
  1325. .ds [A F\*(p] Bieler
  1326. .ds [T An Interpreter for Chandy/Misra's UNITY
  1327. .ds [R internal paper
  1328. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1329. .ds [D 1989
  1330. .][
  1331. .[-
  1332. .ds [F DMN70
  1333. .ds [A O\*(p] Dahl
  1334. .as [A \*(c]B\*(p] Myrhaug
  1335. .as [A \*(m]K\*(p] Nygaard
  1336. .ds [T SIMULA 67 Common Base Language - Publication S-22
  1337. .ds [I Norwegian Computing Center
  1338. .ds [C Oslo
  1339. .ds [D 1970
  1340. .][
  1341. .[-
  1342. .ds [F Gol84
  1343. .ds [A A\*(p] Goldberg
  1344. .ds [T Smalltalk-80: The Interactive Programming Environment
  1345. .ds [I Addison Wesley
  1346. .ds [C Reading, M\&A
  1347. .ds [C Reading, MA
  1348. .ds [D 1984
  1349. .][
  1350. .[-
  1351. .ds [F Gro88
  1352. .ds [A J\*(p] Grosch
  1353. .ds [T Generators for High-Speed Front-Ends
  1354. .ds [V 371
  1355. .ds [J LNCS
  1356. .ds [C Berlin
  1357. .ds [I Springer Verlag
  1358. .nr [P 1
  1359. .ds [P 81-92
  1360. .ds [D Oct. 1988
  1361. .][
  1362. .[-
  1363. .ds [F GrV88
  1364. .ds [A J\*(p] Grosch
  1365. .as [A \*(n]B\*(p] Vielsack
  1366. .ds [T The Parser Generators Lalr and Ell
  1367. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1368. .ds [R Compiler Generation Report No. 8
  1369. .ds [N 8
  1370. .ds [D Apr. 1988
  1371. .][
  1372. .[-
  1373. .ds [F Gro89
  1374. .ds [A J\*(p] Grosch
  1375. .ds [T Ag - An Attribute Evaluator Generator
  1376. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1377. .ds [R Compiler Generation Report No. 16
  1378. .ds [N 16
  1379. .ds [D Aug. 1989
  1380. .][
  1381. .[-
  1382. .ds [F Gro91
  1383. .ds [A J\*(p] Grosch
  1384. .ds [T Ast - A Generator for Abstract Syntax Trees
  1385. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1386. .ds [R Compiler Generation Report No. 15
  1387. .ds [N 15
  1388. .ds [D Sep. 1991
  1389. .][
  1390. .[-
  1391. .ds [F JWM85
  1392. .ds [A K\*(p] Jensen
  1393. .as [A \*(c]N\*(p] Wirth
  1394. .as [A \*(c]A\*(p]\*(a]B\*(p] Mickel
  1395. .as [A \*(m]J\*(p]\*(a]F\*(p] Miner
  1396. .ds [T Pascal User Manual and Report
  1397. .ds [O Third Edition
  1398. .ds [I Springer Verlag
  1399. .ds [C New York
  1400. .ds [D 1985
  1401. .][
  1402. .[-
  1403. .ds [F Joh75
  1404. .ds [A S\*(p]\*(a]C\*(p] Johnson
  1405. .ds [T Yacc \(em  Yet Another Compiler-Compiler
  1406. .ds [R Computer Science Technical Report 32
  1407. .ds [I Bell Telephone Laboratories
  1408. .ds [C Murray Hill, NJ
  1409. .ds [D July 1975
  1410. .][
  1411. .[-
  1412. .ds [F Knu68
  1413. .ds [A D\*(p]\*(a]E\*(p] Knuth
  1414. .ds [T Semantics of Context-Free Languages
  1415. .nr [P 1
  1416. .ds [P 127-146
  1417. .ds [J Mathematical Systems Theory
  1418. .ds [V 2
  1419. .ds [D June 1968
  1420. .ds [N 2
  1421. .][
  1422. .[-
  1423. .ds [F Knu71
  1424. .ds [A D\*(p]\*(a]E\*(p] Knuth
  1425. .ds [T Semantics of Context-free Languages: Correction
  1426. .nr [P 1
  1427. .ds [P 95-96
  1428. .ds [J Mathematical Systems Theory
  1429. .ds [V 5
  1430. .ds [D Mar. 1971
  1431. .][
  1432. .[-
  1433. .ds [F Lam87
  1434. .ds [A D\*(p]\*(a]A\*(p] Lamb
  1435. .ds [T IDL: Sharing Intermediate Representations
  1436. .nr [P 1
  1437. .ds [P 297-318
  1438. .ds [J ACM Trans. Prog. Lang. and Systems
  1439. .ds [V 9
  1440. .ds [N 3
  1441. .ds [D July 1987
  1442. .][
  1443. .[-
  1444. .ds [F Mar90
  1445. .ds [A M\*(p] Martin
  1446. .ds [T Entwurf und Implementierung eines \\*:Ubersetzers von Modula-2 nach C
  1447. .ds [R Diplomarbeit
  1448. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1449. .ds [D Feb. 1990
  1450. .][
  1451. .[-
  1452. .ds [F NNG89
  1453. .ds [A J\*(p]\*(a]R\*(p] Nestor
  1454. .as [A \*(c]J\*(p]\*(a]M\*(p] Newcomer
  1455. .as [A \*(c]P\*(p] Giannini
  1456. .as [A \*(m]D\*(p]\*(a]L\*(p] Stone
  1457. .ds [T IDL: The Language and its Implementation
  1458. .ds [I Prentice Hall
  1459. .ds [C Englewood Cliffs, NJ
  1460. .ds [C Englewood Cliffs
  1461. .ds [D 1989
  1462. .][
  1463. .[-
  1464. .ds [F Par88
  1465. .ds [A J\*(p]\*(a]C\*(p]\*(a]H\*(p] Park
  1466. .ds [T y+: A Yacc Preprocessor for Certain Semantic Actions
  1467. .ds [J SI\&GPLAN Notices
  1468. .ds [V 23
  1469. .ds [N 6
  1470. .nr [P 1
  1471. .ds [P 97-106
  1472. .ds [D 1988
  1473. .][
  1474. .[-
  1475. .ds [F SDD86
  1476. .ds [A J\*(p]\*(a]T\*(p] Schwartz
  1477. .as [A \*(c]R\*(p]\*(a]B\*(p]\*(a]K\*(p] Dewar
  1478. .as [A \*(c]E\*(p] Dubinsky
  1479. .as [A \*(m]E\*(p] Schonberg
  1480. .ds [T Programming with Sets - An Introduction to SETL
  1481. .ds [I Springer Verlag
  1482. .ds [C New York
  1483. .ds [D 1986
  1484. .][
  1485. .[-
  1486. .ds [F WGS89
  1487. .ds [A W\*(p]\*(a]M\*(p] Waite
  1488. .as [A \*(c]J\*(p] Grosch
  1489. .as [A \*(m]F\*(p]\*(a]W\*(p] Schr\\*:oer
  1490. .ds [T Three Compiler Specifications
  1491. .ds [R GMD-Studie Nr. 166
  1492. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1493. .ds [D Aug. 1989
  1494. .][
  1495. .[-
  1496. .ds [F Wir85
  1497. .ds [A N\*(p] Wirth
  1498. .ds [T Programming in Modula-2
  1499. .nr [P 0
  1500. .ds [P 202
  1501. .ds [I Springer Verlag
  1502. .ds [C Heidelberg
  1503. .ds [D 1985
  1504. .ds [O Third Edition
  1505. .][
  1506. .[-
  1507. .ds [F Wir88a
  1508. .ds [A N\*(p] Wirth
  1509. .ds [T Type Extensions
  1510. .ds [J ACM Trans. Prog. Lang. and Systems
  1511. .ds [V 10
  1512. .ds [N 2
  1513. .ds [D Apr. 1988
  1514. .nr [P 1
  1515. .ds [P 204-214
  1516. .][
  1517. .[-
  1518. .ds [F Wir88b
  1519. .ds [A N\*(p] Wirth
  1520. .ds [T From Modula to Oberon
  1521. .ds [J Software\(emPractice & Experience
  1522. .ds [V 18
  1523. .ds [N 7
  1524. .ds [D July 1988
  1525. .nr [P 1
  1526. .ds [P 661-670
  1527. .][
  1528. .[-
  1529. .ds [F Wir88c
  1530. .ds [A N\*(p] Wirth
  1531. .ds [T The Programming Language Oberon
  1532. .ds [J Software\(emPractice & Experience
  1533. .ds [V 18
  1534. .ds [N 7
  1535. .ds [D July 1988
  1536. .nr [P 1
  1537. .ds [P 671-690
  1538. .][
  1539. .bp 1
  1540. .lp
  1541. .b Contents
  1542. .sp
  1543. .xp
  1544.